home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / ctlib100.zip / INSTALL.LZH / LISTS.TXT < prev    next >
Text File  |  1996-10-12  |  6KB  |  94 lines
  1.                        CHAPTER 8
  2.                       Linked Lists
  3.  
  4.  
  5. This chapter discusses in detail the linked list objects included in the Containers Library.  It describes how to use the linked lists and the different types of lists available.
  6.  
  7. In this chapter you will learn:
  8.  
  9.   - What are linked lists?
  10.   - How to use the linked lists
  11.   - The characteristics of each type of linked list
  12.  
  13.  
  14. What are linked lists?
  15.  
  16. Linked lists are simple data structures in which each element contains a pointer to the next, and in some cases, to the previous elements in the list. Since elements must not be physically stored together and elements are dynamic variables created and destroyed as needed, linked lists can shrink or grow dynamically without wasting storage media (e.g. conventional memory).
  17.  
  18. Linked list containers provide all the required structuring for a linked list. You can use TList and TSortedList for creating singly and doubly-linked lists, or use TDoubleList and TDoubleSortedList for creating and optimizing access to doubly-linked lists. Data, however, is stored in another object type that must contain fields for each data element that you want to store. This new object type must be a descendant of TListNode (for singly-linked lists) or TDoubleNode (for doubly-linked lists). You can also use descendant node types for creating the linked lists yourself or accessing the list directly after it has been created by any of the linked list containers.
  19.  
  20.  
  21. Using the linked lists
  22.  
  23. Using the linked lists is just as easy as using the collections.  However, linked list objects assume that data items inserted in the list are pointers to initialized TListNode descendants.  This means that all the data that you store in a linked list must be part of a TListNode descendant that you create.  
  24.  
  25. Creating a data type for storing data in a linked list, is like creating any other object.  The only difference is that instead of using TObject as a parent for the object, you must use TListNode as the parent object:
  26.  
  27.   type
  28.     PContact = ^TContact;
  29.     TContact = object (TListNode)
  30.         FirstName,
  31.         LastName,
  32.         Phone,
  33.         Company : PString;
  34.       constructor Init(ALastName, AFirstName, APhone, 
  35.         ACompany : string);
  36.       destructor Done; virtual;
  37.     end;
  38.  
  39.   constructor TContact.Init(ALastName, AFirstName, APhone,
  40.     ACompany : string);
  41.   begin
  42.     TListNode.Init;
  43.     FirstName := NewStr(AFirstName);
  44.     LastName := NewStr(ALastName);
  45.     Phone := NewStr(APhone);
  46.     Company := NewStr(ACompany);
  47.   end;
  48.  
  49.   destructor TContact.Done;
  50.   begin
  51.     DisposeStr(FirstName);
  52.     DisposeStr(LastName);
  53.     DisposeStr(Phone);
  54.     DisposeStr(Company);
  55.     TListNode.Done;
  56.   end;
  57.  
  58. If you override the Init and Done methods, you must remember to call the Init and Done methods inherited from TListNode.  Otherwise, the list will not work correctly.
  59.  
  60. If you want to have efficient backwards access to the data in your list, you should use a doubly-linked list instead of a normal singly-linked list.  When using doubly-linked lists, however, you must use TDoubleNode as the parent of your data object (e.g. TContact).  Note that a singly-linked list may contain TListNode or TDoubleNode descendants, but should never contain more than one of these node types in the same linked list.  This design greatly reduces code size for the linked list object and increases its speed.  However, this also puts the burden on the programmer to ensure only one type of node (singly or doubly linked) is used in a list and that only TListNode or TDoubleNode descendants are inserted into the list.  A doubly-linked list may contain only TDoubleNode descendants.
  61.  
  62. Once you create the data type for storing your data, you can start using the list.  See the files LISTS1.PAS and LIST2.PAS for complete examples of how to use the linked lists.  
  63.  
  64. Nodes can be also used without TList or TSortedList by directly accessing the nodes' fields and methods (search for TListNode in the reference guides for detailed information).  This eliminates the overhead of container calls, but it then becomes the programmer's responsibility to maintain a position within the linked list.  When a linked list container is not used, nodes may be disposed of by calling Dispose(Node, Done), but you must always keep a pointer to some node in the list so the remaining list items are not lost.  The entire list may be disposed of by calling DisposeList. 
  65.  
  66. Since data items are stored in memory at all times, the use of DoneItem is not required.  However, if you intend to write data-structure independent applications, you must still always use it after retrieving an item from the container.  All lists in the Containers Library are circularly-linked lists.  
  67.  
  68.  
  69. Sorted Lists
  70.  
  71. Sorted versions of TList and TDoubleList are also included in the library.  To use these objects, you must first teach them how to sort your data, which is done by overriding TListNode's KeyOf and Compare methods.  Notice that unlike other sorted containers, you do not override the container's KeyOf and Compare methods but instead, you override the data objects' methods inherited from TNode.  This design makes it easier to create and maintain sorted lists, since all the data specific details are encapsulated within the data object that you create.  The Compare method must not be overridden unless you are using non-strings as the keys of data items.
  72.  
  73. Here is how the TContact object would look when used in a sorted linked list:
  74.  
  75.   type
  76.     PContact = ^TContact;
  77.     TContact = object (TListNode)
  78.         FirstName,
  79.         LastName,
  80.         Phone,
  81.         Company : PString;
  82.       constructor Init(ALastName, AFirstName, APhone, 
  83.         ACompany : string);
  84.       destructor Done; virtual;
  85.       function KeyOf : Pointer; virtual;
  86.     end;
  87.  
  88.   function TContact.KeyOf : Pointer;
  89.   begin
  90.     KeyOf := LastName;
  91.   end;
  92.  
  93. See files LISTS3.PAS and LISTS4.PAS for the complete examples.
  94.